package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.Arrays;

/**
 * (B卷,100分)- 找车位（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 停车场有一横排车位，0代表没有停车，1代表有车。至少停了一辆车在车位上，也至少有一个空位没有停车。
 * <p>
 * 为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的距离是最大的，返回此时的最大距离。
 * <p>
 * 输入描述
 * <p>
 * 一个用半角逗号分割的停车标识字符串，停车标识为0或1，0为空位，1为已停车。
 * 停车位最多100个。
 * <p>
 * 输出描述
 * <p>
 * 输出一个整数记录最大距离。
 * <p>
 * 用例
 * <p>
 * 输入	1,0,0,0,0,1,0,0,1,0,1
 * 输出	2
 * 说明
 * 当车停在第3个位置上时，离其最近的的车距离为2（1到3）。
 * <p>
 * 当车停在第4个位置上时，离其最近的的车距离为2（4到6）。
 * <p>
 * 其他位置距离为1。
 * <p>
 * 因此最大距离为2
 * <p>
 * 题目解析
 * <p>
 * 本题类似于华为OD机试 - 新员工座位（Java & JS & Python）_伏城之外的博客-CSDN博客
 * <p>
 * 本题也可以采用两步走：
 * <p>
 * 正向遍历一遍，确认每个空闲车位的左边的最大停车距离（即当前空闲车位的左边连续空闲车位个数+1）
 * 反向遍历一遍，确认每个空闲车位的右边的最大停车距离（即当前空闲车位的右边连续空闲车位个数+1）
 * 而每个空闲车位的最大停车距离，取其左、右最大停车距离中的较小值。
 * <p>
 * 最后，返回所有空闲车位中的最大停车距离即可。
 * <p>
 * 本题需要注意的是，首尾如果是空闲车位的话：
 * <p>
 * 对第0个空闲车位，其最大停车距离，取得是其右边的停车距离
 * 对第n-1个空闲车位，其最大停车距离，取得是其左边的停车距离
 */
public class FindParkingSpot {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();*/

        int[] nums = Arrays.stream("1,0,0,0,0,1,0,0,1,0,1".split(",")).mapToInt(Integer::parseInt).toArray();
        System.out.println(getResult(nums));
    }

    /**
     * 前缀数组
     *
     * @param nums
     * @return
     */
    public static int getResult(int[] nums) {
        int n = nums.length;

        // leftFree[i] 表示第i个车位的左边空闲车位个数
        int[] leftFree = new int[n];
        for (int i = 1; i < n; i++) {
            if (nums[i] == 1) { // 1表示有车，不能停车
                continue;
            }

            if (nums[i - 1] == 0) {
                leftFree[i] = leftFree[i - 1] + 1;
            } else {
                leftFree[i] = 0;
            }
        }

        // rightFree[i] 表示第i个车位的右边空闲车位个数
        int[] rightFree = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] == 1) { // 1表示有车，不能停车
                continue;
            }

            if (nums[i + 1] == 0) {
                rightFree[i] = rightFree[i + 1] + 1;
            } else {
                rightFree[i] = 0;
            }
        }

        // 如果第0个车位是空闲车位，那么第0个车位的最大距离就是它右边的空闲车位个数
        // 如果第n-1个车位是空闲车位，那么第n-1个车位的最大安全距离就是它左边的空闲车位个数
        int ans = Math.max(rightFree[0], leftFree[n - 1]);

        // 对于第i个车位（i取值1~n-2），其最大距离取min(leftFree[i], rightFree[i])
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] == 1) { // 1表示有车，不能停车
                continue;
            }
            ans = Math.max(ans, Math.min(leftFree[i], rightFree[i]));
        }

        // ans记录的空闲车位数，转化为距离要+1
        return ans + 1;
    }
}
